#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define BUF_SIZE 1024

// 연산자 스택 관련
char *cstack;
int csize;
int ctop;

void cinitstack(int asize) {
	csize = asize;
	cstack = (char *) malloc(csize * sizeof(char));
	ctop = -1;
}

void cfreestack() {
	free(cstack);
}

void cpush(char data) {
	if (ctop < csize - 1) {
		ctop++;
		cstack[ctop] = data;
	}
}

char cpop() {
	if (ctop >= 0) {
		return cstack[ctop--];
	} else {
		return 0;
	}
}

// 숫자 스택 관련
int *dstack;
int dsize;
int dtop;

void dinitstack(int asize) {
	dsize = asize;
	dstack = (int *) malloc(dsize * sizeof(int));
	dtop = -1;
}

void dfreestack() {
	free(dstack);
}

void dpush(int data) {
	if (dtop < dsize - 1) {
		dtop++;
		dstack[dtop] = data;
	}
}

int dpop() {
	if (dtop >= 0) {
		return dstack[dtop--];
	} else {
		return -1;
	}
}

// 연산자 우선 순위 - C의 우선순위와 동일
int getpriority(int op) {
	switch (op) {
	case '(':
		return 0;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	}
	return 100;
}

// 사용자가 입력한 중위 연산표기법을 괄호 연산 및 빠른 연산처리를 위한 후위 표기법으로 변경
int makepostfix(char *post, const char *mid, int *berror) {
	const char *m = mid;
	char *p = post, c;
	cinitstack(BUF_SIZE);

	while (*m) {
		// 숫자 - 그대로 출력하고 뒤에 공백 하나를 출력한다.
		if (isdigit(*m)) {
			while (isdigit(*m))
				*p++ = *m++;
			*p++ = ' ';
		} else {
			// 연산자 - 스택에 있는 자기보다 높은 연산자를 모두 꺼내 출력하고 자신은 푸시한다.
			if (strchr("*/+-", *m)) {
				while (ctop != -1 && getpriority(cstack[ctop]) >= getpriority(
						*m)) {
					*p++ = cpop();
				}
				cpush(*m++);
			} else {
				// 여는 괄호 - 푸시한다.
				if (*m == '(') {
					cpush(*m++);
				} else
				// 닫는 괄호 - 여는 괄호가 나올 때까지 팝해서 출력하고 여는 괄호는 버린다.
				if (*m == ')') {
					for (;;) {
						c = cpop();
						if (c == '(')
							break;
						*p++ = c;
					}
					m++;
				} else {
					m++;
				}
			}
		}
	}
	// 스택에 남은 연산자들 모두 꺼낸다.
	while (ctop != -1) {
		*p++ = cpop();
	}
	*p = 0;
	cfreestack();

	return 0;
}

// 후위 표기법 계산 처리
int calcpostfix(const char *post, int *berror) {
	const char *p = post;
	int num;
	int left, right;

	dinitstack(BUF_SIZE);

	while (*p) {
		// 숫자는 스택에 넣는다.
		if (isdigit(*p)) {
			num = atoi(p);
			dpush(num);
			for (;isdigit(*p); p++) {
				;
			}
		} else {
			// 연산자는 스택에서 두 수를 꺼내 연산하고 다시 푸시한다.
			if (strchr("*/+-", *p)) {
				right = dpop();
				left = dpop();
				switch (*p) {
				case '+':
					dpush(left + right);
					break;
				case '-':
					dpush(left - right);
					break;
				case '*':
					dpush(left * right);
					break;
				case '/':
					// '0'으로 나눈 경우 오류 처리
					if (right == 0) {
						*berror = 1;
					} else {
						dpush(left / right);
					}
					break;
				}
			}
			// 연산 후 또는 연산자가 아닌 경우 다음 문자로
			p++;
		}
	}
	if (dtop != -1) {
		num = dpop();
	} else {
		num = 0;
	}
	dfreestack();
	return num;
}

// 초기 입력값 전달 및 괄호 입력 오류 검증
int calcexp(const char *exp, int *berror) {
	char post[BUF_SIZE];
	const char *p;
	char *operand = "*/+-";
	int count;

	if (berror != NULL) {
		for (p = exp, count = 0; *p; p++) {
			if (*p == '(')
				count++;
			if (*p == ')')
				count--;

			// 입력값 검증
			// 아래의 값 이외의 입력값은 오류 처리 (예: '\n' 등)
			if (!strchr("*/+-0123456789()", *p)) {
				*berror = 1;
			}

			/**
			 /+-*0123456789() 만 입력 가능
			 단항연산자 제외
			 ( 와 ) 는 갯수 같음
			 수식의 첫번째: 숫자,(
			 수식의 마지막: ),숫자
			 ( 의 앞: 연산자,(,
			 ( 의 뒤: 숫자, (
			 ) 의 앞: 숫자, )
			 ) 의 뒤: 연산자, )
			 연산자의 앞: 숫자, )
			 연산자의 뒤: 숫자, (
			 숫자의 앞: 숫자, 연산자, (
			 숫자의 뒤: 숫자, 연산자, )
			 */
			if (*(p - 1) == NULL) {
				if (!isdigit(*p) && *p != '(')
					*berror = 1;
			} else if (*(p + 1) == NULL) {
				if (!isdigit(*p) && *p != ')')
					*berror = 1;
			}

			if (strchr(operand, *p)) {
				if (((!isdigit(*(p - 1)) && *(p - 1) != ')'))
						|| ((!isdigit(*(p + 1)) && *(p + 1) != '(')))
					*berror = 1;
			} else {
				switch (*p) {
				case '(':
					if (((!strchr(operand, *(p - 1)) && *(p - 1) != '('))
							|| ((!isdigit(*(p + 1)) && *(p + 1) != '(')))
						*berror = 1;
					break;
				case ')':
					if (((!isdigit(*(p - 1)) && *(p - 1) != ')'))
							|| ((!strchr(operand, *(p + 1)) && *(p + 1) != ')')))
						*berror = 1;
					break;
				default:
					break;
				}
			}

			if (*berror == 1) {
				return 0;
			}
		}

		// 괄호 입력 오류
		if (count != 0) {
			*berror = 1;
			return 0;
		}
	}

	makepostfix(post, exp, berror);
	return calcpostfix(post, berror);
}
